# 用两个栈实现一个队列
class MyQueue:

    def __init__(self):
        self.stack1=[]
        self.stack2=[]
        self.count=0

    def push(self, x: int) -> None:
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        self.stack1.append(x)
        self.count+=1

    def pop(self) -> int:
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.count-=1
        return self.stack2.pop()

    def peek(self) -> int:
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        top=self.stack2.pop()
        self.stack2.append(top)
        return top

    def empty(self) -> bool:
        return self.count == 0

# 用两个队列实现一个栈
class MyStack:

    def __init__(self):
        self.queue1=[]
        self.queue2=[]
        self.count=0

    def push(self, x: int) -> None:
        self.queue2.append(x)
        while self.queue1:
            self.queue2.append(self.queue1.pop(0))
        self.queue1,self.queue2=self.queue2,self.queue1
        self.count+=1

    def pop(self) -> int:
        self.count-=1
        return self.queue1.pop(0)

    def top(self) -> int:
        return self.queue1[0]

    def empty(self) -> bool:
        return self.count == 0
